package com.freedy.dataStructure.recursion;

/**
 * 八皇后使用二维数组实现
 * @author Freedy
 * @date 2021/3/18 13:42
 */
public class EightQueen {
    //统计摆法的次数
    public static int count=0;
    //最大的皇后个数
    public final static int MAX=12;

    public static void main(String[] args) {
        long l = System.currentTimeMillis();
        int[][] map = new int[MAX][MAX];
        queen(map,0);
        System.out.println("总耗时"+(System.currentTimeMillis()-l));
    }

    /**
     * 主递归方法
     */
    public static void queen(int[][] map, int row) {
        if (row < map.length) {
            for (int i = 0; i < map[row].length; i++) {
                if (map[row][i] == 0) {
                    int[][] backtrackingMap = new int[map.length][map[row].length];//创建一个回溯数组
                    copyArr(map,backtrackingMap);
                    mark(map, row, i);
                    queen(map,row+1);
                    map=backtrackingMap;//进行回溯
                }
            }
        }else {
            count++;
            System.out.println("第"+count+"种解法");
            printMap(map);
        }
    }

    /**
     *对数组做标记
     *  即对同一行、同一列或同一斜线上的元素赋值为2
     *  此时被赋值为2的地方就不能放置皇后
     */
    public static void mark(int[][] map, int x, int y) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (i == x && j == y) {
                    map[i][j] = 1;
                } else if (i == x || j == y || j == -i + x + y||j==i+(y-x)) {
                    map[i][j] = 2;
                }
            }
        }
    }

    /**
     * 打印数组
     * @param map
     */
    public static void printMap(int[][] map) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     *复制数组来方便进行回溯
     */
    public static void copyArr(int[][] origin,int[][] newOne){
        for (int i = 0; i < origin.length; i++) {
            System.arraycopy(origin[i], 0, newOne[i], 0, origin[i].length);
        }
    }

}
